package com.cqs.leetcode.recursion;

import com.cqs.leetcode.TestCaseUtils;

import java.util.Arrays;
import java.util.Random;

public class NextPermutation31 {

    public void nextPermutation(int[] nums) {
        if (nums == null || nums.length <= 1) return;
        final int len = nums.length;
        //找到i，使得[i,len-1]为倒序，而[i-1,i,....,len-1]为非倒序
        int i = nums.length - 1;
        //注意重复的元素
        while (i>=1 && nums[i-1] >= nums[i]) --i;
        //a[i,....,len-1]找到比a[i-1]小的最大元素
        if (i - 1 >= 0){
            int k = len;
            //由于nums[i-1]<nums[i],所以k>=1的时候退出循环
            while (nums[--k] <= nums[i - 1]);
            swap(nums, i-1,  k);
        }
        //[i, ..., len-1]由逆序排列成升序
        int index = i ;
        while (index < (i + len) / 2) {
            swap(nums, index, len -1 - index + i );
            ++index;
        }
    }

    private static void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }

    public static void main(String[] args) {
        NextPermutation31 next = new NextPermutation31();
//        int[] random = random(6);
//        int[] random = {1, 3, 4, 7, 8, 10, 2, 6, 9, 5};
//        int[] random = {1, 3, 4, 7, 8, 10, 9, 6, 5, 2};
        int[] random = {5,4,7,5,3,2};
//        TestCaseUtils.print(random);
        Arrays.sort(random);
        int val = 1;
        for (int i = 0; i < random.length; i++) {
            val *= (i + 1);
        }
        TestCaseUtils.print(random);
        for (int i = 0; i < val; i++) {
            next.nextPermutation(random);
            TestCaseUtils.print(random);
        }
    }

    private static int[] random(int n) {
        Random random = new Random();
        int[] result = new int[n];
        for (int i = 0; i < n; i++) {
            result[i] = i + 1;
        }
        for (int i = 0; i < n; i++) {
            //随机交换
            swap(result, random.nextInt(n), random.nextInt(n));
        }
        return result;
    }
}
